package likou;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/20 06:54
 */
public class _147 {
    public static void main(String[] args) {
        ListNode head = new ListNode(6);
        ListNode next = new ListNode(5);
        head.next = next;
        next.next = new ListNode(3);
        next = next.next;
        next.next = new ListNode(1);
        next = next.next;
        next.next = new ListNode(8);
        next = next.next;
        next.next = new ListNode(7);
        next = next.next;
        next.next = new ListNode(2);
        next = next.next;
        next.next = new ListNode(4);

        ListNode node = insertionSortList(head);

        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }

//    public static ListNode insertionSortList(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode now = head;
//        Deque<ListNode> deque = new LinkedList<>();
//        Deque<ListNode> dequeNext = new LinkedList<>();
//        deque.offerLast(now);
//        now = now.next;
//        while (now != null) {
//            if (now.val < deque.peekLast().val) {
//                while (deque.size() != 0 && now.val < deque.peekLast().val) {
//                    dequeNext.offerLast(deque.pollLast());
//                }
//                deque.offerLast(now);
//                while (dequeNext.size() != 0) {
//                    deque.offerLast(dequeNext.pollLast());
//                }
//            } else {
//                deque.offerLast(now);
//            }
//            now = now.next;
//        }
//        if (deque.size() != 0) {
//            head = deque.pollFirst();
//            now = head;
//            while (deque.size() != 0) {
//                now.next = deque.pollFirst();
//                now = now.next;
//            }
//        }
//        now.next = null;
//        return head;
//    }


    public static ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 1. 获取链表的中间结点，分割链表
        ListNode pre = null, slow = head, fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;//pre为中间节点
            fast = fast.next.next;
            slow = slow.next;//这个slow为中间节点
        }

        pre.next = null;

        // 2. 排序左右部分链表
        ListNode l1 = insertionSortList(head);
        ListNode l2 = insertionSortList(slow);

        // 3. 合并两个有序链表
        return merge(l1, l2);
    }

    public static ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                //cur.next等于小的这个
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}
